#include<stdio.h>
#include<limits.h>
#include<stdbool.h>

/**
 * dijkstra算法，求一个顶点和其他所有顶点的最短距离
 * 从原点开始，找与之相邻的最短的边，然后选定这个边连接的另一个顶点，扩展路径
 * 不断重复下去
 */

#define MAX_VERTEX 9
/**
 * 找最小距离
 * @param dist 距离数组
 * @param sptSet  标记第i个节点是否已经在最短路径树中，若包含在内，那么其距离就不会再更新了
 * @return int 距离最小顶点的下标
 */
int minDistance(int dist[],bool sptSet[]){
    int min=INT_MAX,min_index;
    for(int v=0;v<MAX_VERTEX;v++){//查询最小边
        if(sptSet[v]==false&&dist[v]<=min){
            min=dist[v];
            min_index=v;
        }
    }
    return min_index;
}

void printSolution(int dist[]){
    printf("顶点到源点的最短路径：\n");
    for(int i=0;i<MAX_VERTEX;i++){
        printf("%d -> %d \n",i,dist[i]);
    }
    printf("\n");
}

void dijkstra(int graph[MAX_VERTEX][MAX_VERTEX],int src){
    int dist[MAX_VERTEX];
    bool sptSet[MAX_VERTEX];
    for(int i=0;i<MAX_VERTEX;i++){//初始化距离节点，距离都是无穷大
        dist[i]=INT_MAX;
        sptSet[i]=false;
    }
    dist[src]=0;//原点到自己的距离为0
    for(int count=0;count<MAX_VERTEX-1;count++){
        int u=minDistance(dist,sptSet);//找距离最短的节点
        sptSet[u]=true;//标记距离最短的那个已经是最短了
        for(int v=0;v<MAX_VERTEX;v++){
            //v节点没有找到最短路径 and 从u可以到达v and 从原点可以到达u and 从原点到达u加上u到v比之前的到v的路径距离小
            if(!sptSet[v]&&graph[u][v]&&dist[u]!=INT_MAX&&dist[u]+graph[u][v]<dist[v]){
                dist[v] = dist[u]+graph[u][v];//那么就更新v的距离
            }

        }
    }
    printSolution(dist);
}

int main(void){
      int graph[MAX_VERTEX][MAX_VERTEX] = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };
    dijkstra(graph,0);
    //结果分别是0,4,12,19,21,11,9,8,14
}